package com.le.basic.Sort;

/**
 * 题目: 荷兰国旗问题
 * 给定一个数组arr，和一个数num，
 * 请把小于num的数放在数组的 左边，
 * 等于num的数放在数组的 中间，
 * 大于num的数放在数组的 右边。
 * 要求额外空间复杂度O(1)，时间复杂度O(N)
 */
public class Code_07_NetherlandsFlag {

    public static void partition(int[] arr, int num){
        if (arr == null || arr.length < 2 ){
            return;
        }
        int less = -1;
        int cur = 0;
        int more = arr.length;
        while (cur < more){
            if (arr[cur] < num){ // 如果当前数小于num,则less加一位置与当前数交换
                swap(arr,++less,cur++);
            }else if (arr[cur] > num){ // 如果当前数大于于num,则 more-1位置与当前数交换
                swap(arr, --more,cur);
            }else {
                cur++;
            }
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] test = Code_01_BubbleSort.generateRandomArray(10, 10);
        int random = (int)(Math.random() * 10);
        partition(test,random);
        System.out.println(random);
        Code_01_BubbleSort.printArray(test);
    }
}
